// 2025/4/6
// https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
// 腐烂的橘子

class Solution {
    public:
        void rotting(vector<vector<int>>& grid, vector<vector<int>>& time, int i, int j)
        {
            grid[i][j] = 2;
            if (i > 0 && grid[i - 1][j] == 1 && time[i][j] + 1 < time[i - 1][j])
            {
                time[i - 1][j] = time[i][j] + 1;
                rotting(grid, time, i - 1, j);
            }
            if (i < grid.size() - 1 && grid[i + 1][j] == 1 && time[i][j] + 1 < time[i + 1][j])
            {
                time[i + 1][j] = time[i][j] + 1;
                rotting(grid, time, i + 1, j);
            }
            if (j > 0 && grid[i][j - 1] == 1 && time[i][j] + 1 < time[i][j - 1])
            {
                time[i][j - 1] = time[i][j] + 1;
                rotting(grid, time, i, j - 1);
            }
            if (j < grid[0].size() - 1 && grid[i][j + 1] == 1 && time[i][j] + 1 < time[i][j + 1])
            {
                time[i][j + 1] = time[i][j] + 1;
                rotting(grid, time, i, j + 1);
            }
            grid[i][j] = 1;
        }
    
        int orangesRotting(vector<vector<int>>& grid) {
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> time(m, vector<int>(n, m * n));
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i][j] == 2)
                    {
                        time[i][j] = 0;
                        rotting(grid, time, i, j);
                        grid[i][j] = 2;
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i][j] != 1) continue;
                    if (time[i][j] == m * n)
                        return -1;
                    ans = max(ans, time[i][j]);
                }
            }
            return ans;
        }
    };